// https://leetcode.cn/problems/increasing-triplet-subsequence/description/

// 算法思路总结：
// 1. 基于LIS贪心算法判断是否存在长度为3的递增子序列
// 2. 维护最小末元素的递增序列，优化后续匹配潜力
// 3. 序列长度达到3时立即返回true，提前终止
// 4. 时间复杂度：O(nlogn)，空间复杂度：O(k) k≤3

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    bool increasingTriplet(vector<int>& nums) 
    {
        int m = nums.size();
        if (m <= 2) return false;

        vector<int> subV;
        for (int i = 0 ; i < m ; i++)
        {
            if (subV.empty() || nums[i] > subV.back())
                subV.push_back(nums[i]);
            else
            {
                auto it = lower_bound(subV.begin(), subV.end(), nums[i]);
                *it = nums[i];
            }
        }

        return subV.size() >= 3;
    }
};

int main()
{
    vector<int> v1 = {1,2,3,4,5}, v2 = {5,4,3,2,1};
    Solution sol;

    cout << sol.increasingTriplet(v1) << endl;
    cout << sol.increasingTriplet(v2) << endl;

    return 0;
}